1. Field of the Invention
The present invention relates in general to a network switch for routing traffic between network buses, and in particular to a traffic manager for controlling rates at which an input or output port of the network switch forwards traffic into or away from the network switch.
2. Description of Related Art
A network switch routes data transmissions such as ethernet packets between a set of network buses. A typical network switch includes a set of input ports for receiving network traffic arriving on input buses, a set of output ports for forwarding traffic outward on output buses, and a switch fabric such as a crosspoint switch for routing traffic between the input and output ports.
Network traffic often travels over buses in the form of packets, each including a variable data payload that a source computer sends to a destination computer. Each packet also includes a header conveying data the network devices need to properly route and process the packet. A network switch input port may include a protocol processor for converting each incoming packet to a sequence of cells of uniform size, and a “traffic manager” within the input port for storing the cells in a cell memory until it can forward them through the switch fabric to one of the output ports. An output switch port may include a traffic manager for storing the cells received via the switch fabric in its buffer memory and for later forwarding them to another protocol processor. The output port's protocol processor reassembles each cell into a packet and forwards the packet outward on a network bus.
Each packet is assigned to one of a set of “flows”. All packets assigned to the same flow pass between the same source and destination station and have the same class of service. A flow's “class of service” defines, for example, the maximum and minimum rates at which the network switch forwards traffic assigned to the flow and the forwarding priority the network switch gives to the flow's packets relative to packets of other flows. The traffic manager in a network switch forwards packets of the same flow in the order that it receives them, but may forward packets of high priority flows before forwarding earlier received packets of low priority flows. A flow's maximum and minimum forwarding rate may be established by contractual agreement. For example a network service provider owning a network switch and a network user operating a network station connected to the network switch may agree that packet flows through the switch going to or from that network station will be restricted to specified minimum and maximum rates.
Each packet includes a flow identification number (FIN) in its header identifying the packet's flow. The traffic manager of a network switch input port receiving the incoming packet decodes the packet's FIN to determine which output port is to receive and forward the packet toward the destination station and to determine the rate and priority with which it forwards a packet's cells to an output port. A network switch output port may be able to forward a packet outward to another network switch or to a network station on a selected channel of any of several different network buses, and the traffic manager of a network switch output port decodes the packet's FIN to determine which output bus or bus channel is to convey the packet away from the port. The output port's traffic manager may also decode a packet's FIN to determine a packet's minimum and maximum forwarding rate and priority.
The rate at which an output port forwards packets over a given bus or bus channel is often subject to contractual limits. Hence in addition to controlling forwarding rates and priorities of the various flows to satisfy contractual agreements, the traffic manager of an output switch port may also have to control the rate at which it forwards packets over each output bus channel it accesses so that it remains within contractual limits.
Thus a traffic manager may have to perform two kinds of rate control. First, it must control the rate at which it forwards packets or cells of each flow to maintain the flow rate between desired maximum and minimum limits. Secondly, a traffic manager may have to control the rate at which it forwards packets outward on a particular bus, or each bus channel, irrespective of the flows to which those packets are assigned.
A typical traffic manager first allocates its forwarding bandwidth among its various output resources (such as output busses or bus channels) to make sure that each output resource has sufficient bandwidth to accommodate the flows that make use of that output resource and, conversely, to make sure that the bandwidth allocated to an output resource does not exceed the output resource's contractual or physical bandwidth limitations. The traffic manager then sub-allocates the bandwidth assigned to each output resources among the various flows requiring those output resources, adjusting the forwarding bandwidth allocated to each flow so that it remains within its allowable range.
FIG. 11 illustrates in block diagram form the manner in which a typical traffic manager controls the rate at which cells of each flow are forwarded. The traffic manager includes an output resource rate shaper 120 for allocating cell forwarding bandwidth among a set of N output resources such as for example a set of output bus channels through which an output switch port forwards packets. Output resource rate shaper 120 produces N output signals VOQ(1)-VOQ(N), each associated with one of the N output channels and pulses each signal VOQ(1)-VOQ(N) at the rate at which the output resource is to forward cells. A controller 124 allocates forwarding bandwidth amount output resources by telling rate shaper 120 how frequently it is to pulse each of its output signals.
Each VOQ signal drives a separate flow queue (FQ) rate shaper 122(1)-122(N), each also corresponding to a separate output resource. Each FQ rate shaper 122(1)-122(N) periodically produces the flow queue ID of each active flow queue that is forwarded by the associated output resource. The frequency of each VOQ(1)-VOQ(N) input signal to one of FQ rate shapers 122(1)-122(N) indicates the forwarding bandwidth currently assigned by controller 124 to the corresponding output resource. Each VOQ(1)-VOQ(N) signal tells the FQ rate shaper 122(1)-122(N) how fast it is to generate FQ IDs and therefore how fast cells are to be forwarded by the corresponding output resource. Data from controller 124 tells each FQ rate shaper 122(1)-122(N) how to allocate their corresponding output resource's bandwidths among the flows assigned to those output resources. A corresponding “virtual output queue” 124(1)-124(N) shifts in the FQ IDs produced by each FQ rate shaper 122(1)-122(N). When any of virtual output queues 124(1)-124(N) is not empty, controller 124 shifts the longest-stored FQ ID out of the highest priority non-empty queue via a multiplexer 126. The FQ output of multiplexer 126 indicates the flow queue of the next cell to be forwarded by the traffic manager.
Controller 124 determines how bandwidth is to be allocated among each output resource and amount the flow queues assigned to each output resource based on flow queue data indicating which flow queues are active (i.e., which flow queues have cells currently in the cell buffer waiting to be forwarded) and on programming data indicating the minimum and maximum forwarding rates for each output resource and each flow queue. For example, since an output port may be able to forward packets on any of several output bus channels, its traffic manager first allocates the port's forwarding bandwidth among those bus channels. The traffic manager then sub-allocates the bandwidth allocated to each bus channel among the various flows that are to be forwarded by that bus channel. The traffic manager for an input port has an analogous job; it allocates its forwarding bandwidth among the various output ports to which it may forwarded cells, and then sub-allocates the bandwidth allocated to each output port among the various flows that are to be forwarded to that output port. Since the traffic managers of input and output ports have analogous functions, they are often implemented by identical circuits.
One difficulty with the prior art rate shaping system of FIG. 11 is that the flow queue and output resources rates are not independently adjustable. The switch port's forwarding bandwidth is allocated among its output resources based on the minimum and maximum forwarding rates for each output resource defined by programming data. The forward rate assigned to each output resource is then divided among the flow queues. Thus it is necessary to assign a forwarding rate to an output resource before it is possible to assign forwarding rates to the flow queues assigned to that output resource. This approach may be suitable for use in a network switch output port where the flow rates of output resources (output buses or bus channels) must be shaped. However in a network switch input port, it may not be necessary or desirable to shape an output resource's rate. The output resources of an input port are the output ports to which cells must be forwarded, and in many applications it would be preferable to permit an input switch port to forward cells to output ports via the switch fabric as fast as the output ports can accept them. The need to shape the output resource forwarding rates in a network switch input port can lead to an undesirable reduction in throughput.
What is needed is a bandwidth allocation system for a network switch port which can optionally allocate forwarding bandwidth to flow queues with or without having to shape the forwarding rates of output resources.